gr = require "graphs"

cities = gr.make_graph(0) 
gr.start_naming(cities)

-- this is a utility function.  
-- Given a string, it either returns the 
-- node that already has that name, or else 
-- extends the graph of cities to have one more
-- node, registering  this name as the name of the new node.  
function node_of_city(name)
   local i = gr.node_of_name(cities,name) 
   if i
   then
      return i 
   else 
      gr.extend_graph(cities,1)
      gr.give_node_name(cities,cities.length,name) 
      return gr.node_of_name(cities,name)
   end 
end

-- this is the (simpler) 
-- converse.  Given an integer n,
-- it looks up the name of node n
-- in the cities graph.  

function city_of_node(n) 
   return gr.name_of_node(cities,n)
end

-- Reader function for the data file 
-- entries.  It converse the string 
-- given as the src or dst to a node, 
-- and inserts an edge from the source 
-- node to the dest node and another edge 
-- in the opposite direction.
-- This maintains the graph as undirected.  
-- You can use any edge in either direction.  

function Edge(t) 
   local source = node_of_city(t.src) 
   local dest = node_of_city(t.dst) 

   -- !change on this and the next two lines 
   -- does everything needed to read in 
   -- the edge distances or costs.  
   local distance = t.miles 

   table.insert(cities[source],{src = source, dst = dest, cost = distance}) 
   table.insert(cities[dest],{src = dest, dst = source, cost = distance}) 
end

-- Walk though the cities graph, 
-- printing each city and its immediate neighbors.  
-- Note use of "for i,es in ipairs() do..."
-- This walks through all the integer-value pairs 
-- in the table, binding each integer (node) to i and its 
-- edges to es.  
-- ipairs delivers the pairs in increasing order of the indices, 
-- but stops at the first gap f there are any.  Ignores any table 
-- entries where the index is non-numeric (such as a string).  

function print_edges()
   for i,es in ipairs(cities) do 
      local city_name = gr.name_of_node(cities,i)
      if city_name 
      then 
	 io.write(string.format("\nFrom    %s  	to:   ", city_name))
      else 
	 io.write(string.format("\nNameless city %d  ", i))
      end
      for _,e in pairs(es) do 
	 io.write(string.format(" %s, ", gr.name_of_node(cities,e.dst)))
      end
   end
   io.write("\n\n")
   io.flush()
end

-- Walk through just printing the numeric nodes.

function print_edges_anonymously () 
   for i,es in ipairs(cities) do 
      io.write(string.format("\nFrom    %d  	to:   ", i))
      for _,e in pairs(es) do 
	 io.write(string.format(" %d, ", e.dst))
      end
   end
   io.write("\n\n")
   io.flush()
end   
      

dofile("city_graph.txt")

-- load the search routines 

search = require "hw6_bfs_dfs"

-- Run BFS starting from the named city, 
-- and print out the contents of the result.  

function bfs_results(city_name) 
   search.print_bfs_results(
      cities,
      search.bfs(cities,gr.node_of_name(cities,city_name)))
end 

-- Run dfs_stack starting from the named city, 
-- and print out the contents of the result.  

-- note use of for i,t in pairs(r).  This iterates 
-- through all the pairs even if there are gaps, 
-- but doesnt have to get them in order.  

function dfs_results() 
   local r = search.dfs_stack(cities)
   io.write("City		Disc.		Fin.		Pred.\n\n")
   for i,t in pairs(r) do 
      io.write(string.format("\n %s		%d		%d	%s",
			     gr.name_of_node(cities,i),  
			     t.disc,
			     t.fin, 
			     gr.name_of_node(cities,t.pi) or "none"))
   end 
   io.write("\n"); io.flush()
end 

